하노이의 탑

하노이의 탑 문제 해결 방법

수열의 귀납적 정의와 점화식

점화식 a_n+1= pa_n + q ^{. . .}①, a₁ = a ^{. . .}②를 만족하는 수열 {a_n}의 일반항은

(1) p = 1일 때 a_n = a + (n-1)q ^{. . .}③

(2) p ≠ 1일 때 a_n = p^n-1(a -) + ^{. . .}④

수열 {a_n}에 대해 위의 두 규칙 ①과 ②가 주어지면 ②에 따라 첫째 항이 결정되고,

①에 따라 제 2항이 결정되고, 다시 ①에 따라 제 3항이 결정되고..., 이것을 반복함으로써 일반항 a_n이 결정됩니다.

이렇게 수열을 결정하는 방법을 귀납적 정의라고 하며, 항 사이의 관계를 나타낸 ①과 ②를 점화식이라고 합니다.

문제 이해

하노이의 탑 문제의 목적은 A, B, C 세 장소가 있는 상황에서
n개의 원반이 큰 원반부터 작은 원반의 순서로 A라는 장소에 쌓여 있을 때,

1. 한 번에 한 개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.

이 규칙에 따라 장소 A에 있는 모든 원반을 장소 C(또는 B)로 이동시키는 데 필요한 최소 이동 횟수를 구하는 것입니다.

문제 해결

n개의 원반이 쌓여 있을 때 이것을 앞의 규칙에 따라 다른 장소로 이동시키는 데 필요한 최소 이동 횟수를 a_n이라고 하면,

n개 전부를 장소 A에서 장소 C로 이동시키기 위해서는 다음과 같이 생각해 볼 수 있습니다.

(1) 장소 A에 있는 원반 n-1개를 장소 B에 이동시키는 최소 횟수는 a_n-1입니다.

(2) 장소 A에 남아 있는 한 개의 원반을 장소 C로 이동시키는 횟수는 1회입니다.

(3) 장소 B에 있는 n-1개의 원반을 장소 C에 이동시키는 최소 횟수는 a_n-1입니다.

이때 (1), (2), (3)에 따라 점화식 a_n = a_n-1 + 1 + a_n-1 = 2a_n-1 + 1을 얻을 수 있고,

이는 a_n+1 = 2a_n + 1로 고쳐 쓸 수 있습니다.

이것은 점화식 a_n+1 = pa_n + q에서 p = 2, q = 1인 경우이고, a₁ = 1이므로 이 점화식의 일반항은 a_n = 2ⁿ - 1이 됩니다.